class Solution(object):
    def reinitializePermutation(self, n):
        perm = [i for i in range(n)]
        prev = perm.copy()
        index = 0
        while True:
            index += 1
            now = [0] * n
            for i in range(n):
                if i % 2 == 0:
                    now[i] = perm[i // 2]
                else:
                    now[i] = perm[n // 2 + (i - 1) // 2]
            if now == prev:
                return index
            else:
                perm = now
